`
https://leetcode.cn/problems/longest-palindromic-subsequence/
`

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
  const n = s.length

  // // dp[i][j] 表示 s[i...j] 的最长回文子序列长度
  // const dp = Array.from({ length: n }, () => new Array(n).fill(0))

  // // i === j 时，只有一个字符，必是回文，即 dp 数组对角线上的都是 1
  // for (let i = 0; i < n; i++) {
  //     dp[i][i] = 1
  // }

  // // 最终的结果是 dp[0][n-1] 这里选择反着遍历
  // for (let i = n - 1; i >= 0; i--) {
  //     for (let j = i + 1; j < n; j++) {
  //         // 说明两端新加进来的字符相同，说明都在 lps 内
  //         if (s[i] === s[j]) {
  //             dp[i][j] = dp[i + 1][j - 1] + 2
  //         } else {
  //             // 不相同，则取 s[i+1...j] 和 s[i...j-1] 的最大值
  //             dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
  //         }
  //     }
  // }

  // return dp[0][n - 1]

  // 空间压缩，具体代码可以参照上面的 dp table

  const dp = new Array(n).fill(0)

  for (let i = n - 1; i >= 0; i--) {
    // 对角线都是 1
    dp[i] = 1
    // 保存 dp[i + 1][j - 1]
    // 因为对角线下面的值都是 0，所以可以初始化为 0
    let pre = 0

    for (let j = i + 1; j < n; j++) {
      // 保存 dp[i - 1][j]
      let temp = dp[j]
      if (s[i] === s[j]) {
        dp[j] = pre + 2
      } else {
        // dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
        // 在 dp[j] 计算出来之前，dp[j - 1] -> dp[i][j - 1], dp[j] -> dp[i + 1][j]
        dp[j] = Math.max(dp[j - 1], dp[j])
      }
      // 记录新计算到的给下一个dp[j] 用的 dp[i + 1][j - 1]
      pre = temp
    }
  }

  return dp[n - 1]
};